package com.weng.cloud.service8881.concurrenct.algorithm.recursion.resolver;

import com.weng.cloud.service8881.concurrenct.algorithm.recursion.base.Node;
import com.weng.cloud.service8881.concurrenct.algorithm.recursion.base.Puzzle;
import com.weng.cloud.service8881.concurrenct.algorithm.recursion.base.PuzzleSolver;
import lombok.Setter;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @Author: weng
 * @Date: 2022/7/9
 * @Description: com.weng.cloud.service8881.concurrenct.algorithm.recursion.resolver
 */

public class SequentialPuzzleSolver<P, M> implements PuzzleSolver<P, M> {
    @Setter
    private Puzzle<P, M> puzzle;
    private final Set<P> seen = new HashSet<>();

    @Override
    public List<M> solve() {
        P position = puzzle.initialPosition();
        return search(new Node<P, M>(position, null, null));
    }

    private List<M> search(Node<P, M> node) {
        if (seen.contains(node.getPosition())) {
            return null;
        }
        seen.add(node.getPosition());
        if (puzzle.isGoal(node.getPosition())) {
            return node.asMoveList();
        }
        for (M move : puzzle.legalMoves(node.getPosition())) {
            P position = puzzle.move(node.getPosition(), move);
            Node<P, M> child = new Node<>(position, move, node);
            List<M> result = search(child);
            if (result != null) {
                return result;
            }
        }
        return null;
    }
}
